#include "EventMatcher.h"
#include "Imm.h"
#include "AbsMachCode.h"
#define ARG_LENGTH 4
//#define TEST_SUPREET

vector<string>*
EventMatcher::get1RuleSetSignature(vector<BasePatNode*>* bp){
	vector<string>* signature = new vector<string>();
	vector<BasePatNode*>* result = new vector<BasePatNode*>();
	for (int i=0; i<bp->size(); i++){
		for (int j=0; j<signature->size(); j++)
			if (bp->at(i)->getStringRepresentation() == signature->at(j))
				goto nextSearch;
        if(bp->at(i)) {
		signature->push_back(bp->at(i)->getStringRepresentation());
		result->push_back(bp->at(i));
        }
		nextSearch:;
	}
	sort(signature->begin(), signature->end());
	return signature;

}

void
EventMatcher::printAllRuleSetSignature(vector<vector<BasePatNode*>*>* bp){
	vector<vector<string>*>* signatures = getAllRuleSetSignature(bp);

	for (int i=0; i<signatures->size(); i++)
	{
		cout << "Rule "<<i <<endl;
		for (int j=0; j<signatures->at(i)->size(); j++)
			cout << signatures->at(i)->at(j) << endl;
	}

}


vector<vector<string>*>*
EventMatcher::getAllRuleSetSignature(vector<vector<BasePatNode*>*>* bp){

	vector<vector<string>*>* signatures = new vector<vector<string>*>();

	for (int i=0; i<bp->size(); i++) {
        if(bp->at(i))
		signatures->push_back(get1RuleSetSignature(bp->at(i)));
	}

	return signatures;
}

bool
EventMatcher::sameRuleSetSignature(vector<string>* sign1, vector<string>* sign2){
	if (sign1->size() != sign2->size())
		return false;
	for (int i=0; i<sign1->size(); i++)
		if (sign1->at(i) != sign2->at(i))
			return false;
	return true;
}

bool
EventMatcher::sameAllRulesSetSignature(vector<vector<string>*>* sign1, vector<vector<string>*>* sign2){
	if (sign1->size() != sign2->size())
		return false;
	for (int i=0; i<sign1->size(); i++)
		if (!sameRuleSetSignature(sign1->at(i), sign2->at(i)))
			return false;
	return true;
}

bool
EventMatcher::aRuleHasEPS(vector<BasePatNode*>* aRule){
	for (int i=0; i<aRule->size(); i++ )
		if (aRule->at(i)->kind() ==  BasePatNode::EMPTY || aRule->at(i)->kind() ==  BasePatNode::STAR)
			return true;
	return false;
}

vector<int>*
EventMatcher::ruleMatchedAtState(int state){
	vector<int>* result = new vector<int>();
	vector<vector<BasePatNode*>*>* rules = rulesToStateMapping->at(state);
	for (int i=0; i<rules->size(); i++)
		if (aRuleHasEPS(rules->at(i)))
			result->push_back(i);
	return result;

}



vector<BasePatNode*>*
EventMatcher::doTransition1Rule(vector<BasePatNode*>* bps, string eventName, int ruleNo){

	vector<BasePatNode*>* result = new vector<BasePatNode*>();
	vector<BasePatNode*>* temp;

	for (int i=0; i<bps->size(); i++){
	    if(!bps->at(i))
            continue;
		if (bps->at(i)->kind() == BasePatNode::EMPTY)
			continue;
		temp = bps->at(i)->getNextItemSet(eventName);
		for (int j=0; j<temp->size(); j++)
			if (temp->at(j)->kind() != BasePatNode::UNDEFINED)
				result->push_back(temp->at(j));
		//	else result->push_back(ge_->rule(ruleNo)->pat());
	}
	//result->push_back(ge_->rule(ruleNo)->pat());

	//result->push_back(modifiedRuleSet->at(ruleNo));
	return confineList(result);
}

vector<vector<BasePatNode*>*>*
EventMatcher::doTransitionAllRule(vector<vector<BasePatNode*>*>* bps, string eventName){

	vector<vector<BasePatNode*>*>* result = new vector<vector<BasePatNode*>*>();
	vector<BasePatNode*>* temp;

	for (int i=0; i<bps->size(); i++){
		temp = doTransition1Rule(bps->at(i), eventName, i);
		result->push_back(temp);
	}
	return confineLists(result);
}



//Remove duplicated entries in multiple rules
vector<vector<BasePatNode*>*>*
EventMatcher::confineLists(vector<vector<BasePatNode*>*>* bps){
	vector<vector<BasePatNode*>*>*  results = new vector<vector<BasePatNode*>*>();
	for (int i=0; i<bps->size(); i++)
		results->push_back(confineList(bps->at(i)));
	return results;
}

//Remove duplicated entries within one rule
vector<BasePatNode*>*
EventMatcher::confineList(vector<BasePatNode*>* bp){
	vector<string> signature;
	vector<BasePatNode*>* result = new vector<BasePatNode*>();
	for (int i=0; i<bp->size(); i++){
		for (int j=0; j<signature.size(); j++)
			if (bp->at(i)->getStringRepresentation() == signature.at(j))
				goto nextSearch;
		signature.push_back(bp->at(i)->getStringRepresentation());
		result->push_back(bp->at(i));
		nextSearch:;
	}
	return result;
}

void
EventMatcher::itemSetBasedApproach(bool codeOnly){

	//modifiedRuleSet = new vector<BasePatNode*>();
	rulesToStateMapping = new vector<vector<vector<BasePatNode*>*>*>();
	signaturesToStateMapping = new vector<vector<vector<string>*>*>();

	vector<RuleNode*> rulelist = ge_->rules(); //chaneges for ! operator
	BasePatNode* pat;
	vector<BasePatNode*> *nextItemSet;

	vector<BasePatNode*> *oneRuleSet;



	string event_names;
	if (ge_ && ge_->symTab()) {
		//SymTab* symTab = ge_->symTab();
		SymTab::iterator it = ge_->symTab()->begin();
		for (;it!=ge_->symTab()->end();++it) {
			if ((*it) && (*it)->name() != "any" && (*it)->kind()==SymTabEntry::EVENT_KIND) {
				if(((*it)->name()).length() > 1) {
					if (!codeOnly)
						cout <<"\n\n\nWarning:::::::: Event of length > 1 !!!!!!\n\n\n\n";
				}
				event_names += (*it)->name();
			}
		}
	}

	if (!codeOnly)
		cout << "Total number of events: "<< event_names.length() <<"\n\n";

	vector<int*>* transitionInfo = new vector<int*>();
	int* transitionEntry;

	vector<vector<BasePatNode*>*>* allRuleSet = new vector<vector<BasePatNode*>*>();
	//cout<<"NOT replacement\n";
	for (int i=0; i<rulelist.size(); i++){
		pat = rulelist.at(i)->pat();
		/* changes for ! operator */
		/*if(pat->hasNeg()) {
		    cout<<"---------------------------------------------\n";
            cout<<"before=";
            pat->print(cout,0);
		    pat->replaceNotOperator(event_names);
		    pat->replaceNeg(event_names)->print(cout);
		    cout<<"after="<<pat->getEventPattern(event_names)<<"\n";
		}*/
		/* chanages for ! operator */

		oneRuleSet = new vector<BasePatNode*>();

        if(pat->hasAnyOrOther()) {
		pat = pat->replaceAny(event_names);
		//pat->print(cout);
        }
		if(pat->hasNeg()) {
		pat = pat->replaceNeg(event_names);
		//if(pat)
		//pat->print(cout);
		}



		//oneRuleSet->push_back(pat->replaceNeg(event_names));

        //if(pat->hasAnyOrOther())
		//oneRuleSet->push_back(pat->replaceAny(event_names));

        oneRuleSet->push_back(pat);
		allRuleSet->push_back(oneRuleSet);
		//modifiedRuleSet->push_back(pat);

	    //modifiedRuleSet->push_back(pat->replaceNeg(event_names));

        //if(pat->hasAnyOrOther())
        //modifiedRuleSet->push_back(pat->replaceAny(event_names));
	}

	//cout << signaturesToStateMapping->size();
	//printAllRuleSetSignature(allRuleSet);

	getStateFromAllRuleSet(allRuleSet);
	int nextState;
	vector<int>* rulesMatched;

	for (int j=0; j<rulesToStateMapping->size(); j++){

		transitionEntry = (int*)malloc(event_names.length()* sizeof(int));
		transitionInfo->push_back(transitionEntry);

		if (!codeOnly)
			cout << "\n----- Current state: "<<j<<"------\n";
		allRuleSet = rulesToStateMapping->at(j);


		if (!codeOnly) {
			printAllRuleSetSignature(allRuleSet);
		}

		for (int i=0; i<event_names.length(); i++){
			nextState = getStateFromAllRuleSet(doTransitionAllRule(allRuleSet, event_names.substr(i, 1)));
			transitionEntry[i] = nextState;
			if (!codeOnly) {
				cout << "On input "<< event_names.substr(i, 1) << ", go to state "<<nextState<<"." <<endl;
			}
		}

		rulesMatched = ruleMatchedAtState(j);
		for (int i=0; i<rulesMatched->size(); i++) {
			if (!codeOnly) {
				cout << "Rule "<<rulesMatched->at(i) << " matched!!"<<endl;
			}
		}

	}



	int stateBase = 0;

	if (!codeOnly)
		cout << "\n\n==============  Machine Code for event matching ==============\n\n";

	cout << "//stateBase memory offset: "<<stateBase<<endl;


	//cout << "MOVL HALT R000" << endl;
/*	cout << "MOVI 0 R000" << endl;

	for (int i=0; i<rulesToStateMapping->size(); i++){
		for (int j=0; j<256; j++)
			cout << "STI R000 "<< i*256+j << endl;
	}
*/
	for (int j=0; j<rulesToStateMapping->size(); j++){


		cout << "// Memory Location "<<j*256+stateBase<<" (space of state "<<j<<"):"<<endl;
		//cout << "MOVI "<< stateBase + j*256 << " R000" <<endl;

		transitionEntry = transitionInfo->at(j);

		for (int i=0; i<event_names.length(); i++){
			nextState = transitionEntry[i];
			cout << "//" <<"\tLocation "<<((int)event_names.at(i))+j*256+stateBase << " (offset "<<((int)event_names.at(i))<<"): Label S"<< nextState <<endl;

			cout << "MOVL S"<< nextState << " R000" << endl;
			cout << "STI R000 " << ((int)event_names.at(i))+j*256+stateBase <<endl;
		}
		cout <<endl;

	}
	// call init global
	cout << "// init stack and base pointer" << endl;
	cout << "START_OVER: MOVI 10000" << SP << endl;	// SP
	cout << "MOVI " << SP << LR << endl;		// SP -> BP
	cout << "MOVL HALT R003" << endl;
	cout << "PRTS \"Enter a string:\\n\"" <<endl;
	cout << "JMP init_global" << endl;
	cout << "HALT: PRTS \"Halt\\n\"" << endl;

	cout << "HALT2: JMP HALT2" << endl;

	//cout << "MOVL INNERHALT R003" << endl ;
	//cout << "PRTS \"Press enter\\n\"" <<endl;
	//cout << "IN R000" << endl;
	//cout << "MOVL START_OVER R000" << endl;
	cout << "JMP START_OVER" << endl;
	//cout << "INNERHALT: JMPI R003"<<endl;

	for (int j=0; j<rulesToStateMapping->size(); j++){

		cout << "S"<<j<<": ";

		rulesMatched = ruleMatchedAtState(j);
		for (int i=0; i<rulesMatched->size(); i++) {
			ImmCodes* m = new ImmCodes();
			RuleNode *rule = rulelist.at(rulesMatched->at(i));
			InvocationNode* invoke = new InvocationNode( rule->func(), NULL);
			m->add(ImmCode::CALL, (void*)invoke, NULL);
			AbsMachCode::generate(m, cout);
			cout << "// call _action_" << rulesMatched->at(i)<<endl;
		}

		cout << "MOVI "<<j*256+stateBase<<" R000"<<endl;
		cout << "IN R001"<<endl;
		cout << "ADD R001 R000 R002"<<endl;
		cout << "LDI R002 R000" << endl;
		cout << "JMPCI EQ R000 0 R003" << endl;
		cout << "JMPI R000"<<endl<<endl;


	}

	cout << endl;
	cout << endl;




}


int
EventMatcher::getStateFromAllRuleSet(vector<vector<BasePatNode*>*>* res){


	vector<vector<string>*>* inputSignature = getAllRuleSetSignature(res);

	int i;
	for (i=0; i<signaturesToStateMapping->size(); i++)
		if (sameAllRulesSetSignature(signaturesToStateMapping->at(i), inputSignature))
			return i;

	rulesToStateMapping->push_back(res);
	signaturesToStateMapping->push_back(inputSignature);

	return i;
}

/*
int
EventMatcher::getStateFromREs(vector<BasePatNode*>* res, vector<int>* invoked_list2){
	//vector<vector<string*>*>* rulesToStateTable;
	vector<vector<string*>*>::const_iterator it = rulesToStateTable->begin();

	//vector<string*> oneRuleTable;
	vector<string*>::const_iterator it2;

	vector<BasePatNode*>::const_iterator res_it = res->begin();
	vector<string*>* re_strings = new vector<string*>();
	ostringstream os;


	vector<BasePatNode*>* new_res = new vector<BasePatNode*>();
	vector<int>* invoked_list = new vector<int>();

	int z;
	for (z=0; (res_it) != res->end(); ++res_it, z++){
		if ((*res_it)->kind() == BasePatNode::UNDEFINED){
			//rulesToStateStorage->at(0)->at(z)->print(os);
			//new_res->push_back(rulesToStateStorage->at(0)->at(z));
			(*res_it)->print(os);
			new_res->push_back(*res_it);
		}
		else if ((*res_it)->kind() == BasePatNode::EMPTY){
			invoked_list->push_back(z);
//			rulesToStateStorage->at(0)->at(z)->print(os);
//			new_res->push_back(rulesToStateStorage->at(0)->at(z));
			(*res_it)->print(os);
			new_res->push_back(*res_it);
		}
		else{
			(*res_it)->print(os);
			new_res->push_back(*res_it);
		}
		re_strings->push_back( new string(os.str()) );
	}



	vector<string*>::const_iterator rs_it = re_strings->begin();


//	cout << "\n\n\n\n";
	int index = 0;


	for (; (it) != rulesToStateTable->end(); (it++), index++){
		it2 = (*it)->begin();
		if (re_strings->size() != (*it)->size())
			goto nextState;
		for (rs_it = re_strings->begin(); (it2) != (*it)->end(); it2++, rs_it++){
			if (*(*it2) != *(*rs_it)){
//				cout << "\nComparing "<< *(*it2) << "  and  " <<  *(*rs_it) <<"\n";
				goto nextState;
			}
		}
		return index;
		nextState:;
	}



	rulesToStateTable->push_back(re_strings);
	rulesToStateStorage->push_back(new_res);

	for (int i=0; i<invoked_list->size(); i++)
		cout << "state "<< index <<" will invoke action of rule "<<invoked_list->at(i)<<endl;

	//rulesToStateStorage->push_back(res);

	return index;

}


vector<BasePatNode*>*
EventMatcher::derivativeOfSetOfBasePat(vector<BasePatNode*>* inBP, string wrt, vector<int>* invoked_list){

	vector<BasePatNode*>* outBP = new vector<BasePatNode*>();
	vector<BasePatNode*>::const_iterator inBP_it = inBP->begin();

	BasePatNode* pat;
	//vector<int>* invoked_list = new vector<int>();


	for (int z=0; inBP_it != (inBP)->end(); ++inBP_it, z++) {
		pat = (*inBP_it)->derivativeWRTname(wrt);

		if (pat->kind() == BasePatNode::EMPTY){
			invoked_list->push_back(z);
			pat = rulesToStateStorage->at(0)->at(z);//->derivativeWRTname(wrt);
		}
		else if (pat->kind() == BasePatNode::UNDEFINED){
			pat = rulesToStateStorage->at(0)->at(z);//->derivativeWRTname(wrt);
		}

		outBP->push_back(pat);
	}

	return outBP;

}


void EventMatcher::testDerivative(){
	rulesToStateTable = new vector<vector<string*>*>();
	rulesToStateStorage = new vector<vector<BasePatNode*>*>();
	//actionInvoke = new vector<vector<int>* >();

	stateCounter = 0;
	vector<RuleNode*> rulelist = ge_->rules();
	vector<RuleNode*>::const_iterator it = rulelist.begin();
	BasePatNode* pat, *ptr;

	int lastUpdatedStatus = 0;
	int latestStatus = 0;

	vector<BasePatNode*>* res = new vector<BasePatNode*>();

	vector<vector<vector<int>*>*>* actionInvoked = new vector<vector<vector<int>*>*>();
	vector<vector<int>*>* actionIn1state;

	it = rulelist.begin();
	//cout << "num of rules = " << rulelist.size() << "\n\n\n";
	for (;it!=rulelist.end();++it) {

		//cout << res->size() << "\n\n\n\n\n\n";
		res->push_back((*it)->pat());
		ptr = (*it)->pat();
		//cout << "\n\n"; ptr->print(cout); cout << "\n\n";
		//cout << res->size() << "\n\n\n\n\n\n";
	}

	getStateFromREs(res);

	//cout << "index is :  "<< getStateFromREs(res);
	//cout << "index is :  "<< getStateFromREs(res);

	string event_names;
	if (ge_ && ge_->symTab()) {
		//SymTab* symTab = ge_->symTab();
		SymTab::iterator it = ge_->symTab()->begin();
		for (;it!=ge_->symTab()->end();++it) {
			if ((*it) && (*it)->name() != "any" && (*it)->kind()==SymTabEntry::EVENT_KIND) {
				if(((*it)->name()).length() > 1)
					cout <<"\n\n\nWarning:::::::: Event of length > 1 !!!!!!\n\n\n\n";
				event_names += (*it)->name();
			}
		}
	}

	cout << "Total number of events: "<< event_names.length() <<"\n\n";

	vector<int*>* transitionInfo = new vector<int*>();
	vector<int>* actionInvokedForanEvent;

	for (int j=0; j<rulesToStateStorage->size(); j++){

		int* transitionEntry = (int*)malloc(event_names.length()* sizeof(int));
		actionIn1state = new vector<vector<int>*>();
		actionInvoked->push_back(actionIn1state);

		transitionInfo->push_back(transitionEntry);
		int nextState;

		res = rulesToStateStorage->at(j);

		for (int k=0; k<event_names.length(); k++){
			actionInvokedForanEvent = new vector<int>();
			actionIn1state->push_back(actionInvokedForanEvent);
			nextState = getStateFromREs(derivativeOfSetOfBasePat(res, event_names.substr(k, 1), actionInvokedForanEvent));
			transitionEntry[k] = nextState;
		}
//		getStateFromREs(derivativeOfSetOfBasePat(res, "b"));

	}


	cout << "\n\n=====================================\n\n";
	cout << "total number of states: " << rulesToStateStorage->size() << endl;
	for (int j=0; j<rulesToStateStorage->size(); j++){
		cout << "\n\n-------------  State " << j << " ---------------------\n";

		res = rulesToStateStorage->at(j);

		for ( int i=0; i<res->size(); i++) {
			res->at(i)->print(cout);
			cout <<endl;
		}

		cout <<"\nTransitions and Invocation\n";
		for ( int i=0; i<event_names.length(); i++) {
			cout << "on input "<< event_names.substr(i, 1) << ":\n";
			for ( int k=0; k<actionInvoked->at(j)->at(i)->size(); k++) {
				cout << " - Rule " << actionInvoked->at(j)->at(i)->at(k) << " invoked. "<<endl;
			}
			cout << " - go to state " << (transitionInfo->at(j))[i] <<endl;
		}

	}



}

<<<<<<< .mine
//SUPREET IMPLEMENTATION
=======
*/



bool EventMatcher::getEventPatFromAST() {
    //get the event patterns
    string event_names;
    string event_pats;
    if (ge_ && ge_->symTab()) {
        //SymTab* symTab = ge_->symTab();
		SymTab::iterator it = ge_->symTab()->begin();
		for (;it!=ge_->symTab()->end();++it) {
			if ((*it) && (*it)->name() != "any" && (*it)->kind()==SymTabEntry::EVENT_KIND) {
			    if(((*it)->name()).length() > 1)
			    return false;
				event_names += (*it)->name();
			}
		}
	}
    //event_names_ = event_names;
    if(event_names.length() == 0)
    return false;
    event_names_ = event_names;

    vector<RuleNode*> rulelist = ge_->rules();
	vector<RuleNode*>::const_iterator it = rulelist.begin();
	for (;it!=rulelist.end();++it) {
		if ((*it) && (*it)->pat()) {
            event_pats = (*it)->pat()->getEventPattern(event_names_);
		    //event_pats_.push_back(event_pats);
            event_pat_list_.push_back(new EventPat(event_pats,event_names,getNextLabel()));
		}

	}
	if(event_pat_list_.size() == 0)
	return false;
	/*if(event_pats_.size() == 0)
	return false;*/
	return true;
}

void EventMatcher::startForEventPat() {
    //event_names_="abc";
    //string input= "a:b|b|a*|c:a*:b";
    if(!getEventPatFromAST()) {
        cout<<"error in getting event patterns\n";
        return;
    }
    vector<EventPat*>::iterator itep;
    EventPat* ep ;
    string input="";
    string names="";
    for(itep=event_pat_list_.begin();itep!=event_pat_list_.end();++itep) {
        //input+= "|" + (*it);
        ep = (*itep);
        if(!ep)
        continue;
        ep->addState(ep->getRegEx());
        ep->createDFAForEventPat(ep->getRegEx());
        /*cout<<"--------------------------------------\n";
        cout<<"event pattern="<<ep->getRegEx()<<"\n";
        cout<<"event names="<<ep->getEventNames()<<"\n";
        ep->printStates();
        ep->printStateTran();
        cout<<"--------------------------------------\n";*/

    }
    for(itep=event_pat_list_.begin();itep!=event_pat_list_.end();++itep) {
        ep = (*itep);
        if(!ep)
        continue;
        input += "|" + ep->getRegEx();
        names = ep->getEventNames();

    }
    input = input.substr(1);
        //event_names_ = names;
        //event_regex_ = input;
        EventPat* ep_all = new  EventPat(input,names,getNextLabel());
        final_pat_ = ep_all;
        final_pat_->addState(input);
        final_pat_->createDFAForEventPat(input);
        cout<<"--------------------------------------\n";
        cout<<"event pattern="<<final_pat_->getRegEx()<<"\n";
        cout<<"event names="<<final_pat_->getEventNames()<<"\n";
        final_pat_->printStates();
        final_pat_->printStateTran();
        cout<<"--------------------------------------\n";
        printStateTranWithAction();
        cout<<"--------------------------------------\n";
}

void EventPat::createDFAForEventPat(string regex) {
    string temp_state;
    vector <string> action_list;
    int final;
    for(int i=0;i<event_names_.length();i++) {

        temp_state = dtranForExpr(regex,event_names_[i],&final);
        //cout<<temp_state<<"\n";
        if(temp_state.length() ==0)
        continue;
        if(temp_state == "#")
        continue;
        if(isFinalState(temp_state)) {
            addFinalState(temp_state);
        }
        addStateTran(regex,event_names_[i],temp_state);
        if(!isStatePresent(temp_state)) {
            addState(temp_state);
            createDFAForEventPat(temp_state);
        }
    }
}

string EventPat::dtranForExpr(string p,char a,int *f) {
    string r1,r2,left,op,right;

    if(p.length()==0)
        return "#";
    if(p.length() > 1 && (p[0] == '$' || p[p.length()-1] == '$') ) {
        if(p[0] == '$')
            return dtranForExpr(p.substr(2),a,f);
        else if(p[p.length()-1] == '$')
            return dtranForExpr(p.substr(0,p.length()-2),a,f);
    }
    //if(p.length() > 2 && p[0] == '(' && p[p.length()-1]==')') {
    if(p.length() > 2 && checkForParenthesis(p)) {
        return dtranForExpr(p.substr(1,p.length()-2),a,f);
    }

    //}
    if(p.length() ==1 ) {
        if(p[0] == a) {
        //*f=1;
        return "$";// epsilon
        }
        else
        return "#";// phi
    }
    int i = getExprWithParenthesis(p);
    if(i==0)
    return "#";
    if(p.length() <= i+1) {
        //error
        return "#";
    }
    else if(p.length() == i+2) {
        // no right
        left = p.substr(0,i+1);
        op = p.substr(i+1,1);
        right = "";
    }
    else {
    left = p.substr(0,i+1);
    op = p.substr(i+1,1);
    right = p.substr(i+2);
    }
    //cout<<"left:"<<left<<"op:"<<op<<"right"<<right<<"\n";

    if(right.length()==0 && op=="*") {
        r1  = dtranForExpr(left,a,f);
        if (r1 == "#")
            return "#";
        else if(r1 == "$") {
            //final state
            //*f=1;
            return (left + op);
        }
        else
            return (r1 + left + op);
    }
    else if(right.length() > 0) {
    //look for next character
        if(op==":") {
            r1 = dtranForExpr(left,a,f);
            if (r1 == "#")
                return "#";
            else if(r1 == "$") {
                //final state;
                //*f=1;
                r1 = right;
            }
            else
            r1 = r1 + ":" + right;
            if(eps(left)) {
            r2 = dtranForExpr(right,a,f);
            //if(r2=="$")
                //*f=1;
            return concat(r1,r2);
            }
            else
            return r1;
        }
        else if(op == "|") {
            r1 = dtranForExpr(left,a,f);
            r2 = dtranForExpr(right,a,f);
            return concat(r1,r2);
        }
    }
    return "#";
}

bool EventPat::checkForParenthesis(string p) {
    string s="";
    stack<char> st;
    for(int i=0;i<p.length();i++) {

         if(p[i]=='(')
            st.push('(');
         else if(p[i]==')')  {
            while (st.top() != '(') {
                 //cout<<st.top()<<"\n";
                st.pop();
            }
            if(st.top() == '(')
            st.pop();

        }
        else
        st.push(p[i]);
    }

    if(st.empty())
        return true;
    else
        return false;


}

int EventPat::getExprWithParenthesis(string p) {
    //cout<<p;
    string s="";
    stack<char> st;
    if(p[0]=='(')
        st.push('(');
    for(int i=1;i<p.length();i++) {
        if(p[i]=='(')
            st.push('(');
        else if(p[i]==')')  {
            while (st.top() != '(') {
            st.pop();
            }
            st.pop();
        }
        else
            st.push(p[i]);
        if(st.empty())
        return i;
    }
    return 0;

}

bool EventPat::eps(string p) {
    //after the end of parenthesis do u find a *
    string op,left,right;
    if(p.length() == 0)
    return false;
    if(p == "$")
    return true;
    if(p.length() > 2 && checkForParenthesis(p)) {
        return eps(p.substr(1,p.length()-2));
    }
    if(p[p.length()-1] == '*')
    return true;
    int i = getExprWithParenthesis(p);
    if(i == 0 || p.length() <= i+1) {
        //error
        return false;
    }
    else if(p.length() == i+2) {
        // no right
        left = p.substr(0,i+1);
        op = p.substr(i+1,1);
        right = "";
    }
    else {
        left = p.substr(0,i+1);
        op = p.substr(i+1,1);
        right = p.substr(i+2);
    }

    if(op== "*")
    return true;
    else if(op == ":")
    return (eps(left) && eps(right));
    else if(op == "|")
    return (eps(left) || eps(right));

    return false;
}

string EventPat::concat(string r1,string r2) {
            if(r1 == "#" && r2 =="#")
                return "#";
            else if(r1 == "#" && r2!="#")
                return r2;
            else if(r1 != "#" && r2=="#")
                return r1;
            else if(r1 == "$" && r2 =="$")
                return r2;
            else
            return ( r1 + "|" + r2 );
}
int  EventPat::stringToInt(string regex) {
    //int x=0;
    vector<string> states = getStates();
    for(int i=0;i<states.size();i++) {
        if(regex == states[i])
        return i;
    }
    /*for(int i=0;i<regex.length();i++)
            x+=(regex[i]*(i+1));*/
    return 0;
}
void EventPat::addState(string regex) {
    states_.push_back(regex);
    state_num++;

}

void EventPat::addFinalState(string regex) {
    final_states_.push_back(regex);

}
void EventPat::addStateTran(string srcState,char c,string dstState) {

    state_tran_.push_back(new StateTran(srcState,c,dstState));
}
bool EventPat::isStatePresent(string regex) {
        vector<string>::iterator it;
        it = find(states_.begin(),states_.end(),regex);
        if (it == states_.end())
            return false;
        else
            return true;
}
void EventPat::printStates() {
    vector<string>::iterator it;
    vector<string>::iterator it2;

    /*cout<<"start ";
    int i=0;
    for(it=states_.begin();it!=states_.end();++it) {
        cout<<"state="<<stringToInt((*it));
        //cout<<"state="<<++i;
        it2 = find(final_states_.begin(),final_states_.end(),(*it));
        if (it2 !=final_states_.end())
            cout<<"(final_state)";
        cout<<"\n";
    }*/
    cout<<"total states:"<<states_.size()<<"\n";

}
void StateTran::printStates() {
    //cout<<"("<<stringToInt(srcState_)<<"->"<<c_<<")"<<"="<<stringToInt(dstState_)<<"\n";
}
void EventPat::printStateTran() {
    vector<StateTran*>::iterator its;
    vector<string>::iterator it;
    for(its=state_tran_.begin();its!=state_tran_.end();++its) {
        //(*its)->printStates();

        cout<<"("<<stringToInt((*its)->getSrcState())<<"->"<<(*its)->getC()<<")"<<"="<<stringToInt((*its)->getDstState());
        it = find(final_states_.begin(),final_states_.end(),(*its)->getDstState());
        if (it !=final_states_.end()) {
            cout<<"(final)";
            //cout<<(*its)->getDstState()<<"\n";
        }
        /*State *st = searchForFinal((*its)->getDstState());
        if(st)
        st->getActions();*/
        cout<<"\n";
    }
}

bool EventPat::isFinalState(string p) {
    if(p=="$")
        return true;
    if(p.length() > 1 && (p[0] == '$' || p[p.length()-1] == '$') ) {
        return true;
    }
    if(eps(p))
        return true;
    return false;

}
void EventMatcher::printStateTranWithAction() {
    vector<StateTran*>::iterator its;
    vector<string>::iterator it;
    vector<StateTran*> state_tran_ = final_pat_->getStateTran();
    vector<string> final_states_ = final_pat_->getFinalStates();
    for(its=state_tran_.begin();its!=state_tran_.end();++its) {
        //(*its)->printStates();

        cout<<"("<<final_pat_->stringToInt((*its)->getSrcState())<<"->"<<(*its)->getC()<<")"<<"="<<final_pat_->stringToInt((*its)->getDstState());
        it = find(final_states_.begin(),final_states_.end(),(*its)->getDstState());
        if (it !=final_states_.end()) {

            cout<<getActionsForState((*its)->getDstState());
        }
        /*State *st = searchForFinal((*its)->getDstState());
        if(st)
        st->getActions();*/
        cout<<"\n";
    }
}
string EventMatcher::getActionsForState(string regex) {
    vector<EventPat*>::iterator its;
    vector<string>::iterator itf;
    vector<string> final_states_;
    EventPat *pat;
    string action_label = "{";
    for(its=event_pat_list_.begin();its!=event_pat_list_.end();++its) {
        pat = *its;
        if(pat) {
            final_states_ = pat->getFinalStates();
            for(itf=final_states_.begin();itf!=final_states_.end();++itf) {
                if(regex == (*itf) ) {
                    action_label+=(pat->getAction() + ";");
                    break;
                }
            }
        }
     }
     return action_label + "}";
}


